﻿#pragma once
#include "Index.h"

class IMaxScoreFromRemovingStones
{
public:
    /**
     * title: 移除石子的最大得分.
     * keys: 贪心 数学
     * https://leetcode.cn/problems/maximum-score-from-removing-stones/
     *
     * 你正在玩一个单人游戏，面前放置着大小分别为 a​​​​​​、b 和 c​​​​​​ 的 三堆 石子。
     * 每回合你都要从两个 不同的非空堆 中取出一颗石子，并在得分上加 1 分。
     * 当存在 两个或更多 的空堆时，游戏停止。给你三个整数 a 、b 和 c ，返回可以得到的 最大分数 。
     */
    virtual int maximumScore(int a, int b, int c) = 0;
};

class MaxScoreFromRemovingStones
{
public:
    class Greedy:public IMaxScoreFromRemovingStones
    {
    public:
        /**
         * stones中的数从小到大
         * 每次从较大的后两个数减1，维持stones的有序
         * 当stones[1]==0,也就是前2个数为0时，游戏结束
         * 返回进行的回合数
         *
         * 时间:O(n)
         */
	    int maximumScore(int a, int b, int c) override
	    {
            if (a < 0 || b < 0 || c < 0)
                return 0;

            std::vector<int> stones = {a,b,c};
            std::sort(stones.begin(), stones.end());

            int turns = 0;
            while(stones[1]>0)
            {
                stones[1] -= 1;
                stones[2] -= 1;

                if (stones[0] > stones[1])
                    std::swap(stones[0], stones[1]);
                if (stones[1] > stones[2])
                    std::swap(stones[1], stones[2]);
                turns++;
            }
            return turns;
	    }
    };

    class Math:public IMaxScoreFromRemovingStones
    {
    public:
        /**
         * 设 x<=y<=z,
         *
         * 1、当 x+y <= z时，最大的回合数为 x+y
         *
         * 2、当 x+y >  z时，每次x,y中的较大者和z匹配,当z为0时，此时剩余的回合数为 (x'+y')/2
         *  x'=x-k1
         *  y'=y-k2
         *  k1+k2=z
         * 总的回合数为 z+(x'+y')/2 =(x+y+z)/2
         *
         * z是3个数中最大的值 =max{a,b,c}
         * x+y是3个数中较小的两个值= a+b+c-max{a,b,c}
         * 时间:O(1)
         */
	    int maximumScore(int a, int b, int c) override
	    {
            if (a < 0 || b < 0 || c < 0)
                return 0;

	    	const int z = std::max<>({ a,b,c });
            const int xy = a + b + c - z;

            if (xy <= z)
                return xy;
            else
                return (xy + z) >> 1;
	    }
    };
};